﻿//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>

#include "common.h"

void print_int_array(int arr[], int n) // 打印数组
{
	int i;
	for (i = 0; i < n; ++i)
		printf("%d ", arr[i]);
	printf("\n");
}

void bubble_sort(int arr[], int n) // n 表示数组排序的前 n 位
{ // 冒泡排序，时间复杂度 O(n^2),稳定排序
	int i, j, temp, swapped;
	//for (i = 0; i < n - 1; ++i)
	//{
	//	swapped = 0; // 标记是否进行交换
	//	for (j = 0; j < n - i - 1; ++j)
	//		if (arr[j] > arr[j + 1]) // 交换条件
	//		{
	//			temp = arr[j];
	//			arr[j] = arr[j + 1];
	//			arr[j + 1] = temp;
	//			swapped = 1; // 标记进行交换
	//		}
	//	if (0 == swapped) // 如果没有进行交换，说明已经排序完成，退出循环
	//		break;
	//}

	for (i = n - 1; i >= 0; --i) // 便于理解的写法
	{
		swapped = 0; // 标记是否进行交换
		for (j = 0; j < i; ++j)
			if (arr[j] > arr[j + 1]) // 交换条件
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				swapped = 1; // 标记进行交换
			}
		if (0 == swapped) // 如果没有进行交换，说明已经排序完成，退出循环
			break;
	}
}

void selection_sort(int arr[], int n) // n 表示数组排序的前 n 位
{ // 选择排序，时间复杂度 O(n^2)，不稳定排序
	int i, j, min_idx, max_idx, temp;
	//for (i = 0; i < n - 1; ++i)
	//{
	//	min_idx = i; // 假设第一个元素是最小的
	//	for (j = i + 1; j < n; ++j)
	//		if (arr[j] < arr[min_idx]) // 寻找最小元素的下标
	//			min_idx = j;
	//	if (min_idx != i) // 如果最小元素不是第一个元素，交换位置
	//	{
	//		temp = arr[i];
	//		arr[i] = arr[min_idx];
	//		arr[min_idx] = temp;
	//	}
	//}

	//for (i = 0; i < n - 1; ++i)
	//{ // 反向选择排序
	//	max_idx = i; // 假设第一个元素是最大的
	//	for (j = i + 1; j < n; ++j)
	//		if (arr[j] > arr[max_idx]) // 寻找最大元素的下标
	//			max_idx = j;
	//	if (max_idx != i) // 如果最大元素不是第一个元素，交换位置
	//	{
	//		temp = arr[i];
	//		arr[i] = arr[max_idx];
	//		arr[max_idx] = temp;
	//	}
	//}

	for (i = n - 1; i >= 0; --i)
	{ // 选择排序，选择大的元素
		max_idx = i; // 假设最后面的元素是最大的
		for (j = 0; j < i; ++j)
		{
			if (arr[j] > arr[max_idx]) // 寻找最大元素的下标
			{
				max_idx = j;
			}
		}
		if (max_idx != i) // 如果最大元素不是最后面的元素，交换位置
		{
			temp = arr[i];
			arr[i] = arr[max_idx];
			arr[max_idx] = temp;
		}
	}
}

void insertion_sort(int arr[], int n) // n 表示数组排序的前 n 位
{ // 插入排序，时间复杂度 O(n^2)，稳定排序
	int i, j, temp;
	for (i = 1; i < n; ++i)
	{
		temp = arr[i]; // 待插入的元素
		j = i - 1; // 从 i-1 开始向前搜索插入位置
		while (j >= 0 && arr[j] > temp) // 找到插入位置
		{
			arr[j + 1] = arr[j]; // 元素后移
			--j; // 继续向前搜索
		}
		arr[j + 1] = temp; // 插入元素
	}
}

void quick_sort(int arr[], int left, int right)
// left 表示数组排序的左边界下标，right 表示数组排序的右边界下标
{ // 快速排序，时间复杂度 O(nlogn)，不稳定排序
	int start, end, pivot;
	start = left;
	end = right;
	pivot = arr[left]; // 选取第一个元素作为基准
	while (left < right)
	{
		while (left < right && arr[right] >= pivot)
			// 右边界向左搜索小于基准的元素
			--right;
		arr[left] = arr[right]; // 把右边界元素放到左边界
		while (left < right && arr[left] <= pivot)
			// 左边界向右搜索大于基准的元素
			++left;
		arr[right] = arr[left]; // 把左边界元素放到右边界
	}
	arr[left] = pivot; // 把基准放到中间
	if (start < left - 1) // 左边有元素
		quick_sort(arr, start, left - 1); // 递归左边
	if (right + 1 < end) // 右边有元素
		quick_sort(arr, right + 1, end); // 递归右边
}

void merge(int arr[], int left, int mid, int right)
// left 表示数组排序的左边界下标，
// mid 表示数组排序的中间下标，
// right 表示数组排序的右边界下标
{ // 合并两个有序数组
	int i, j, k;
	float temp[100] = { 0.0f }; // temp 为临时数组
	i = left;
	j = mid + 1;
	k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j])
		{
			temp[k] = arr[i];
			++k;
			++i;
		}
		else
		{
			temp[k] = arr[j];
			++k;
			++j;
		}
	}
	while (i <= mid)
		temp[k++] = arr[i++]; // 同上一个 while 循环的 if 部分
	while (j <= right)
		temp[k++] = arr[j++];
	for (i = left; i <= right; ++i)
		arr[i] = temp[i];
}

void merge_sort(int arr[], int left, int right)
// left 表示数组排序的左边界下标，right 表示数组排序的右边界下标
{ // 归并排序，时间复杂度 O(nlogn)，稳定排序
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; // 取中间下标
		merge_sort(arr, left, mid); // 递归左边
		merge_sort(arr, mid + 1, right); // 递归右边
		merge(arr, left, mid, right); // 合并
	}
}
